from functools import cache


class Solution:
    def numberOfPowerfulInt(self, start: int, finish: int, limit: int, s: str) -> int:

        low = str(start)
        high = str(finish)
        n = len(high)
        low = '0' * (n - len(low)) + low  # 低位补前导0，使和higt数位对齐
        diff = n - len(s)  # 能填充多少位数

        # 基础班：不考虑前导0
        # 当前位i，
        # limit_low,表示前面填的数字是否都是n对应位上的，如果为true，那么当前至少为int(s[i])，否者为0
        # limit_high：表示前面填的数字是否都是n对应位上的，如果为true，那么当前至多为int(s[i])，否者为9
        @cache
        def dfs(i, limit_low, limit_high):
            if i == n:
                return 1

            # 第i个数位可以从哪枚举，枚举范围
            # 如果对数位有其他约束，应当只在下面的for 循环做限制
            lo = int(low[i]) if limit_low else 0
            hi = int(high[i]) if limit_high else 9
            res = 0
            if i < diff:
                for d in range(lo, min(hi, limit) + 1):  # 当前数位的取值范围
                    # 控制下一个的范围，两个条件：看前面（limit_low）是否true and 当前（d==lo）是否为true，有一个不满足，都为false，表示范围可以随便取
                    res += dfs(i + 1, limit_low and d == lo, limit_high and d == hi)
            else:
                # 超过了diff，必须填 int(s[i-diff])
                x = int(s[i - diff])
                if lo <= x <= min(hi, limit):  # 只有一种结果
                    res += dfs(i + 1, limit_low and x == lo, limit_high and x == hi)
            return res

        return dfs(0, True, True)

        # 扩展版：支持前导0
        # in_num 表示前面是否填了数字（是否跳过），如果是true，那么当前位可以从0开始，如果为false，那么我们可以跳过，或者从1开始填数字
        # @cache
        # def dfs(i,limit_low,limit_high,is_num):
        #     if i==n:
        #         return 1 if is_num else 0

        #     res=0
        #     if not is_num and low[i]=='0': # 前面填的都是0，limit_low 一定是True
        #         # 这一位也可以填0
        #         if i<diff:
        #             res+=dfs(i+1,True,False,False)

        #     # 第i个数位可以从哪枚举
        #     # 如果对数位有其他约束，应当只在下面的for 循环做限制
        #     lo=int(low[i]) if limit_low else 0
        #     hi=int(high[i]) if limit_high else 9

        #     d0 = 0 if is_num else 1
        #     if i<diff:
        #         for d in range(max(d0,lo),min(hi,limit)+1):
        #             res+=dfs(i+1,limit_low and d==lo,limit_high and d==hi,True)
        #     else:
        #         # 必须填 int(s[i-diff])
        #         x=int(s[i-diff])
        #         if max(d0,lo)<=x<=min(hi,limit):
        #             res=dfs(i+1,limit_low and x==lo,limit_high and x==hi,True)
        #     return res

        # return dfs(0,True,True,False)

